﻿using System;
using System.Collections.Generic;
using System.Text;


/*
 
// 快速查找可行走路线。	
// 构建四叉树，往里面填入所有可行走路点的索引(x,y)
如果没有QuadTree tree，创建一个
	传入V，Width，Height
	如果发现tree.v==null，那么将V值村给tree.v = V
	否则，
		将tree.v传给Next[tree.v.x/width, tree.v.y/height]四叉树，然后跳转到第一个步，递归开始
		将V传给Next[V.x/width, V.y/height]四叉树，然后跳转到第一个步，递归开始	

// 查找某个点(x,y)附近一个可行走的点
QuadTree tree
	如果tree.v == null，那么将四叉树索引为：tree.Next[x/width,y/height]，跳转到第一个步，递归开始。
	否则，返回tree.v

 
 */
namespace point2bmp
{
    public class QuadTree
    {
        QuadTree[] Next = null;
        MyPoint SavedV = null;

        // 将v填充到矩形内，矩形范围为[left,top,width,height]
        public void Fill(MyPoint v, int left, int top, int width, int height)
        {
            if (SavedV == null)
            {
                SavedV = v;
                return;
            }

            if (Next == null)
            {
                Next = new QuadTree[4];
            }
            FillNext(SavedV, left, top, width, height);
            SavedV = null;
            FillNext(v, left, top, width, height);
        }

        // 查找一个距离自己较近的
        public MyPoint Search(MyPoint v, int left, int top, int width, int height)
        {
            if (SavedV != null)
                return SavedV;
            if (Next == null)
                return null;

            int x, y;
            int quadLeft, quadTop, quadWidth, quadHeight;
            GetChildQuad(v, left, top, width, height, out x, out y, out quadLeft, out quadTop, out quadWidth, out quadHeight);
            
            int idx = x + y * 2;
            if (Next[idx] == null)
                return null;

            return Next[idx].Search(v, quadLeft, quadTop, quadWidth, quadHeight);
        }


        void FillNext(MyPoint v, int left, int top, int width, int height)
        {
            int x, y;
            int quadLeft, quadTop, quadWidth, quadHeight;
            GetChildQuad(v, left, top, width, height, out x, out y, out quadLeft, out quadTop, out quadWidth, out quadHeight);

            // 将值填充到定位块中。
            int idx = x + y * 2;
            if (Next[idx] == null)
            {
                Next[idx] = new QuadTree();
            }
            Next[idx].Fill(v, quadLeft, quadTop, quadWidth, quadHeight);
        }

        void GetChildQuad(MyPoint v, int left, int top, int width, int height,
            out int x, out int y,
            out int quadLeft, out int quadTop, out int quadWidth, out int quadHeight
            )
        {            
            // 将区域划分成4块，每块的大小是：
            quadWidth = (width+1) / 2;  // 加1的目的是防止漏边界，比如3*3大小的区块，分成4块后，应该是区块的宽度依次将是2,1,2,1
            quadHeight = (height+1) / 2;

            // 将v定位到4块中的一块。
            x = (v.x - left) / quadWidth;
            y = (v.y - top) / quadHeight;

            // 获取定位块的left,top
            quadLeft = left + x * quadWidth;
            quadTop = top + y * quadHeight;
        }
    }
}

